package com.example.algorithmdemo.leetcode;

import java.util.HashSet;

public class LeetCode {
    static class Link{
       private Link next;
       private int value;//这里的int可以是泛型
        public Link(int value,Link next){
            this.value = value;
            this.next = next;
        }
    }

    /**
     * 求链表的交点，有交点则返回对应的节点
     * @return null则表示无交点
     */
    public static Link leetCode_link_intersection_test(){
        Link h_next_next_next_next = new Link(5,null);
        Link h_next_next_next = new Link(4,h_next_next_next_next);
        Link h_next_next = new Link(3,h_next_next_next);
        Link h_next = new Link(2,h_next_next);
        //链表1：1->2->3->4->5->null
        Link link1 = new Link(1,h_next);
        //链表2：6->3->4->5->null
        Link link2 = new Link(6,h_next_next);
        //链表1，2的交点为结点3
        Link result =  link_intersection(link1,link2);
        result =  link_intersection2(link1,link2);
        result =  link_intersection3(link1,link2);
        return result;
    }

    /**
     * 方法1：暴力循环，两次循环 时间复杂度为0(N^2),空间复杂度为O(1)
     * 方法2：set集合判断，基于红黑树，时间复杂度为0(N),空间复杂度为O(NLogN)
     * 方法3：计算长度差，长的优先移动差值步，看后面是否相等，时间复杂度为0(N),空间复杂度为O(1)
     * 方法三为最优算法
     * @param link1
     * @param link2
     * @return
     */
    private static Link link_intersection(Link link1,Link link2){
        ///方法1：暴力循环
        Link curLink1 = link1;
        while (curLink1 != null){
            Link curLink2 = link2;
            while (curLink2 != null){
                if (curLink1.equals(curLink2)){
                    System.out.println("找到了交点" + curLink1.toString());
                    return curLink1;
                }
                curLink2 = curLink2.next;
            }
            curLink1 = curLink1.next;
        }
        return null;
    }

    private static Link link_intersection2(Link link1,Link link2){
        ///方法2：利用HashSet实现
        Link curLink1 = link1;
        HashSet<Link> hashSet = new HashSet<>();
        while (curLink1 != null){
            hashSet.add(curLink1);
            curLink1 = curLink1.next;
        }
        Link curLink2 = link2;
        while (curLink2 != null){
            if (hashSet.contains(curLink2)){
                System.out.println("找到了交点" + curLink2.toString());
                return curLink2;
            }
            curLink2 = curLink2.next;

        }
        return null;
    }

    private static Link link_intersection3(Link link1,Link link2){
        ///先遍历查找链表长度，链表长的链表优先走高度差
        int l1_length = getLinkLength(link1);
        int l2_length = getLinkLength(link2);
        if (l1_length > l2_length){
            Link moveNode = moveMoreNode(link1,l1_length - l2_length);
            //此时moveNode与l2遍历比较是否相等
            while (moveNode != null && link2 != null){
                if (moveNode.equals(link2)){
                    System.out.println("找到了交点" + moveNode.toString());
                    return moveNode;
                }
                moveNode = moveNode.next;
                link2 = link2.next;
            }
        }else if(l1_length == l2_length){
            Link moveNode = moveMoreNode(link1,l1_length - l2_length);
            while (moveNode != null && link2 != null){
                if (moveNode.equals(link2)){
                    System.out.println("找到了交点" + moveNode.toString());
                    return moveNode;
                }
                moveNode = moveNode.next;
                link2 = link2.next;
            }
        }else {
            Link moveNode = moveMoreNode(link1,l2_length - l1_length);
            while (moveNode != null && link1 != null){
                if (moveNode.equals(link1)){
                    System.out.println("找到了交点" + moveNode.toString());
                    return moveNode;
                }
                moveNode = moveNode.next;
                link1 = link1.next;
            }
        }
        return null;
    }
    private static Link moveMoreNode(Link link,int moveCount){
        Link cur = link;
        int count = 0;
        while (count < moveCount){
            count += 1;
            cur = cur.next;
        }
        return cur;
    }
    private static int getLinkLength(Link link){
        Link cur = link;
        int length = 0;
        while (cur != null){
            length += 1;
            cur = cur.next;
        }
        return length;
    }
    /**
     * 测试列表反转方法
     */
    public static void testReverseLink(){
        Link h_next_next_next_next = new Link(5,null);
        Link h_next_next_next = new Link(4,h_next_next_next_next);
        Link h_next_next = new Link(3,h_next_next_next);
        Link h_next = new Link(2,h_next_next);
        Link head = new Link(1,h_next);

        ///使用三个指针反转链表
        Link reverseHead = reverseLink(head);
        System.out.println(reverseHead);
        ///使用递归反转整个链表
        Link recursionHead = recursion_Link(reverseHead);
        System.out.println(recursionHead);
    }
    /**
     * 反转链表
     */
    /**
     * 循环遍历链表反转链表
     * @param head
     * @return
     */
    private static Link reverseLink(Link head){
        Link next,pre = null;
        Link cur = head;
        while (cur != null){
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    /**
     * 递归反转链表
     * 化解为子问题，注意结束return条件
     * @param head
     * @return
     */
    private static Link recursion_Link(Link head){
        ///如果为空链表或者链表长度为1直接返回
        if (head == null || head.next == null){
            return head;
        }
        ///化解子问题，递归调用不断入栈 调用到最后
        Link newHead =  recursion_Link(head.next);
        //出栈返回，避免成环head.next = null
        head.next.next = head;
        head.next = null;
        return newHead;
    }
}
